/**

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
CBTInserter.get_root() 将返回树的头节点。
 

示例 1：

输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/complete-binary-tree-inserter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。



 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

 //////////////////////////////////////
 //解法一 ; 利用完全二叉树紧凑的特性
class CBTInserter {
private:
    vector<TreeNode* > tree;
    void insert_level(TreeNode* root)
    {
        deque<TreeNode *> mydeque;
        mydeque.push_back(root);
        tree.push_back(root);
        while(!mydeque.empty())
        {
            TreeNode* node = mydeque.front();
            if(node->left)
            {
                mydeque.push_back(node->left);
                tree.push_back(node->left);
            }
            if(node->right)
            {
                mydeque.push_back(node->right);
                tree.push_back(node->right);
            }
            mydeque.pop_front();
        }

    }
public:
    CBTInserter(TreeNode* root) {
        if(root)
            insert_level(root);
    }
    
    int insert(int v) {
        TreeNode* newNode = new TreeNode(v);
        tree.push_back(newNode);
        int index = tree.size()-1;
        int parentIndex = (index-1)/2;

        if(parentIndex >= 0)
        {
            if(parentIndex * 2 +1 == index)
                tree[parentIndex]->left = newNode;
            else
                tree[parentIndex]->right = newNode;
        }
        return tree[parentIndex]->val;
    }
    
    TreeNode* get_root() {
        if(! tree.empty())
            return tree[0];
        else
            return 0;
    }
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(v);
 * TreeNode* param_2 = obj->get_root();
 */